package Top200;

/**
 * @author zhangmin
 * @create 2022-02-22 10:46
 * 贪心；每次在能跳到的最远的位置之前的位置遍历，找看下一步能跳到的最远变为新的end
 */
public class jump45 {
    public int jump(int[] nums) {
        int n=nums.length;
        int end=0,farthest=0;
        int jumps=0;
        for (int i = 0; i < n - 1; i++) {
            farthest=Math.max(nums[i]+i,farthest);
            if (end==i){
                jumps++;
                end=farthest;
            }
        }
        return jumps;
    }
}
